package 算法.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
 * @author lchenglong
 * @date 2022/4/21
 */
public class Offer14_I {

    public static void main(String[] args) {
        Offer14_I instance = new Offer14_I();
        int ans = instance.cuttingRope(3);
        System.out.println(ans);
    }
    public int cuttingRope(int n) {
        if (n<=2)return 1;
        if (n == 3)return 2;
        return Math.max(dfs(n/2)*dfs(n-n/2),dfs(n/2-1)*dfs(n-(n/2-1)));
    }

    int dfs(int n){
        if (n<=0)return 1;
        else if (n <=3) return n;
        else {
            int max = Math.max(dfs(n/2)*dfs(n-n/2),dfs(n/2-1)*dfs(n-(n/2-1)));
            return Math.max(n,max);
        }
    }
}
